﻿using UnityEngine;
using System.Collections.Generic;
using System;

public enum ConvexPolyDirection
{
	CW,
	CCW,
	ZERO,
	MULTI_CW,
	MULTI_CCW,
	OTHER
}

[System.Serializable]
public class ConvexPoly : ICloneable
{
	public const float DEFAULT_THRESHOLD = MathUtils.EPSILON;

	public List<Vector2> points = new List<Vector2>();

	public int pointCount { get { return points.Count; } }
	public int segmentCount { get { return points.Count; } }

	public ConvexPoly()
	{
	}

	public ConvexPoly( ConvexPoly other )
	{
		points = new List<Vector2>( other.points );
	}

	public object Clone()
	{
		return new ConvexPoly( this );
	}

	public void Scale( float s )
	{
		for ( int i = 0; i < points.Count; i++ )
			points[ i ] *= s;
	}

	public bool IsConvex()
	{
		if ( points.Count < 3 )
			return false;

		float sign = 0f;
		for ( int i = 0; i < points.Count; i++ )
		{
			int prevIndex = MathUtils.WrapIndex( i - 1, points.Count );
			int nextIndex = MathUtils.WrapIndex( i + 1, points.Count );

			Vector2 p_prev = points[ prevIndex ];
			Vector2 p_curr = points[ i ];
			Vector2 p_next = points[ nextIndex ];

			Vector2 E1 = p_curr - p_prev;
			Vector2 E2 = p_next - p_curr;

			float cross = MathUtils.CrossProduct( E1, E2 );
			
			if ( i == 0 )
			{
				sign = Mathf.Sign( cross );
				continue;
			}

			if ( sign * cross < 0f )
				return false;
		}

		return true;
	}

	public ConvexPolyDirection Direction()
	{
		float walk = WalkRotation();
		
		if ( Mathf.Abs( walk - MathUtils.TWO_PI ) < MathUtils.EPSILON )
			return ConvexPolyDirection.CW;

		if ( Mathf.Abs( walk + MathUtils.TWO_PI ) < MathUtils.EPSILON )
			return ConvexPolyDirection.CCW;
		
		if ( Mathf.Abs( walk ) < MathUtils.EPSILON )
			return ConvexPolyDirection.ZERO;

		if ( walk > MathUtils.TWO_PI )
			return ConvexPolyDirection.MULTI_CW;

		if ( walk < -MathUtils.TWO_PI )
			return ConvexPolyDirection.MULTI_CCW;

		return ConvexPolyDirection.OTHER;
	}

	private float WalkRotation()
	{
		float currAngle = 0f;
		for ( int i = 0; i < points.Count; i++ )
		{
			int prevIndex = MathUtils.WrapIndex( i - 1, points.Count );
			int nextIndex = MathUtils.WrapIndex( i + 1, points.Count );

			Vector2 p_prev = points[ prevIndex ];
			Vector2 p_curr = points[ i ];
			Vector2 p_next = points[ nextIndex ];

			Vector2 E1 = p_curr - p_prev;
			Vector2 E2 = p_next - p_curr;

			currAngle += MathUtils.SingnedAngle( E1, E2 );
		}
		return currAngle;
	}

	public void AddPoint( Vector2 v, float threshold = DEFAULT_THRESHOLD )
	{
		if ( IsDouble( v, threshold ) )
		{
			//Debug.Log( "[" + v.x + ", " + v.y + "] NO, DOUBLE" );
			return;
		}

		int removeCount = 0;
		int insertCount = 0;

		if ( points.Count < 2 )
		{
			points.Add( v );
			return;
			//insertCount++;
			//goto debug_info;
		}

		// Находим первую и последнюю вершину, с которыми нужно соединить новую точку

		int prevCollapseIndex = -1;
		int nextCollapseIndex = -1;

		for ( int i = 0; i < points.Count; i++ )
		{
			int prevIndex = MathUtils.WrapIndex( i - 1, points.Count );
			int nextIndex = MathUtils.WrapIndex( i + 1, points.Count );

			Vector2 p = points[ i ];
			Vector2 p_prev = points[ prevIndex ];
			Vector2 p_next = points[ nextIndex ];

			Vector2 E1 = p - p_prev;
			Vector2 L1 = v - p_prev;

			Vector2 E2 = p_next - p;
			Vector2 L2 = v - p;

			float cross1 = MathUtils.CrossProduct( E1, L1 );
			float cross2 = MathUtils.CrossProduct( E2, L2 );

			if ( cross1 < 0f && cross2 >= 0f )
			{
				prevCollapseIndex = i;
			}
			else if ( cross1 >= 0f && cross2 < 0f )
			{
				nextCollapseIndex = i;
			}
			else if ( cross1 >= 0f && cross2 >= 0f )
			{
				points.RemoveAt( i );
				removeCount++;
				i--;
			}
		}

		if ( nextCollapseIndex != -1 && prevCollapseIndex != -1 )
		{
			int insertIndex = MathUtils.WrapIndex( prevCollapseIndex + 1, points.Count );
			points.Insert( insertIndex, v );
			insertCount++;
		}

		//debug_info:
		//Debug.Log( "[" + v.x + ", " + v.y + "] OK\n" + "  Removes: " + removeCount + "  Inserts: " + insertCount );
	}

	public void AddRect( Rect rect, float threshold = DEFAULT_THRESHOLD )
	{
		AddPoint( new Vector2( rect.xMin, rect.yMin ), threshold );
		AddPoint( new Vector2( rect.xMax, rect.yMin ), threshold );
		AddPoint( new Vector2( rect.xMax, rect.yMax ), threshold );
		AddPoint( new Vector2( rect.xMin, rect.yMax ), threshold );
	}

	public bool IsInside( Vector2 v )
	{
		for ( int i = 0, j = points.Count - 1; i < points.Count; j = i, i++ )
		{
			Vector2 v1 = points[ j ];
			Vector2 v2 = points[ i ];

			Vector2 E = v2 - v1;
			Vector2 L = v - v1;

			float cross = MathUtils.CrossProduct( E, L );
			if ( cross < 0f )
				return false;
		}

		return true;
	}

	public bool IsDouble( Vector2 v, float threshold = 0.01f )
	{
		foreach ( Vector2 p in points )
			if ( Mathf.Abs( v.x - p.x ) < threshold && Mathf.Abs( v.y - p.y ) < threshold )
				return true;

		return false;
	}

	public float GetCombinedTolerance( params Vector2[] additionalPoints )
	{
		float tolerance = 1f;
		foreach ( Vector2 p in points )
			tolerance = Mathf.Max( tolerance, p.x, p.y );
		foreach ( Vector2 p in additionalPoints )
			tolerance = Mathf.Max( tolerance, p.x, p.y );
		return tolerance * MathUtils.EPSILON;
	}

	public void Bisect( Vector2 v1, Vector2 v2, bool leftside = false )
	{
		List<Vector2> oldPoints = points;
		points = new List<Vector2>();

		Vector2 L = v2 - v1;
		
		float tolerance = GetCombinedTolerance( v1, v2 );

		// Проходим по всем сегментам и клипим их
		for ( int i = 0; i < oldPoints.Count; i++ )
		{
			int nextIndex = MathUtils.WrapIndex( i + 1, oldPoints.Count );

			Vector2 p1 = oldPoints[ i ];
			Vector2 p2 = oldPoints[ nextIndex ];
			
			Vector2 clipVertex = new Vector2();
			if ( Intersection.Intersect_LineSegment( v1, v2, p1, p2, ref clipVertex ) )
			{
				AddPoint( clipVertex, tolerance );
			}

			Vector2 D = p1 - v1;
			float LxD = MathUtils.CrossProduct( L, D );
			if ( leftside )
			{
				if ( LxD > tolerance )
					AddPoint( p1, tolerance );
			}
			else
			{
				if ( LxD < -tolerance )
					AddPoint( p1, tolerance );
			}
		}
	}

	[Obsolete]
	public void Bisect_Wrong( Vector2 v1, Vector2 v2, bool leftside = false )
	{
		float tolerance = GetCombinedTolerance( v1, v2 );

		int clipIndex1 = -1;
		int clipIndex2 = -1;

		// Проходим по всем сегментам и клипим их
		for ( int i = 0; i < segmentCount; i++ )
		{
			int newClipIndex = ClipSegment( i, v1, v2, tolerance );
			if ( newClipIndex != -1 )
			{
				if ( clipIndex1 == -1 )
					clipIndex1 = newClipIndex;
				clipIndex2 = newClipIndex;
			}
		}

		// Прямая не пересекает полигон
		if ( clipIndex1 == -1 )
			return;

#if false
		// После того как есть индексы, нужно установить верный их порядок
		if ( clipIndex1 != clipIndex2 )
		{
			if ( Vector2.Dot( points[ clipIndex2 ] - points[ clipIndex1 ], v2 - v1 ) < 0f )
			{
				if ( !leftside )
					MathUtils.Swap( ref clipIndex1, ref clipIndex2 );
			}
			else
			{
				if ( leftside )
					MathUtils.Swap( ref clipIndex1, ref clipIndex2 );
			}
		}
#endif

		// Потом удаляем все ребра слева или справа от бесектора
		Vector2 L = v2 - v1;
		for ( int i = points.Count - 1; i >= 0; i-- )
		{
			if ( i == clipIndex1 || i == clipIndex2 )
				continue;

			Vector2 p = points[ i ];
			float cross = MathUtils.CrossProduct( L, p - v1 );
			if ( leftside && ( cross <= tolerance ) || !leftside && ( cross >= -tolerance ) )
			{
				points.RemoveAt( i );
			}
		}
	}

	[Obsolete]
	private int ClipSegment( int segment, Vector2 v1, Vector2 v2, float tolerance )
	{
		int nextIndex = MathUtils.WrapIndex( segment + 1, points.Count );

		Vector2 p1 = points[ segment ];
		Vector2 p2 = points[ nextIndex ];

		Vector2 L = v2 - v1;
		Vector2 D1 = p1 - v1;
		float LxD1 = MathUtils.CrossProduct( L, D1 );
		
		// Прямая проходит через вершину 1
		if ( Mathf.Abs( LxD1 ) < tolerance )
			return segment;
		
		Vector2 D2 = p2 - v1;
		float LxD2 = MathUtils.CrossProduct( L, D2 );

		// Прямая проходит через вершину 2
		if ( Mathf.Abs( LxD2 ) < tolerance )
			return nextIndex;

		// Прямая не пересекает сегмент
		if ( LxD1 * LxD2 > 0f )
			return -1;

		// Клипим нормально
		Vector2 clipVertex = new Vector2();
		if ( !Intersection.Intersect_Lines( v1, v2, p1, p2, ref clipVertex ) )
			throw new UnityException( "Прямая и сегмент параллельны, такого не должно быть" );

		points.Insert( nextIndex, clipVertex );
		return nextIndex;
	}

	public void DebugPrint( string prefix, bool useLogfile, bool useConsole )
	{
		bool isConvex = IsConvex();
		string dir = Direction().ToString();

		if ( useLogfile )
		{
			foreach ( Vector2 p in points )
				Log.WriteLine( prefix + p );

			Log.WriteLine( prefix + ( isConvex ? "good" : "invalid" ) );
			Log.WriteLine( prefix + dir );
		}

		if ( useConsole )
		{
			foreach ( Vector2 p in points )
				Debug.Log( prefix + p );

			Debug.Log( prefix + ( isConvex ? "good" : "invalid" ) );
			Debug.Log( prefix + dir );
		}
	}

#if false
	/// <summary>
	/// Переменная sign хранит "знак" полуплоскости прямой, в которой находится сегмент:
	///  а) -1  - слева (отрицательный CrossProduct)
	///  б)  0  - прямая пересекает сегмент или лежит прямо на нем
	///  в)  1  - справа (положительный CrossProduct)
	/// Значение ненулевое только когда прямая проходит через одну вершину или не пересекает сегмент.
	/// Когда пересекает, то одно из двух значений rightIn или rightOut равно истине.
	/// </summary>
	public struct ClipInfo
	{
		public int clipIndex;	// индекс клипнутой вершины
		public int side1;		// "знак" полуплоскости первой вершины (1 - правая)
		public int side2;		// "знак" полуплоскости первой вершины (1 - правая)
		public bool rightIn;	// сегмент "заходит" в правую полуплоскость прямой (из левой)
		public bool rightOut;	// сегмент "выходит" из правой полуплоскости прямой (в левую)
		public bool parallel;
	};

	/// <summary>
	/// Прямая [v1,v2] режет сегмент многоугольника и возвращает:
	///  а) индекс новой вершины
	///  б) индекс уже существующей вершины
	///  в) -1, если прямая не пересекает сегмент
	/// Также переменная sign хранит "знак" полуплоскости прямой, в которой находится сегмент:
	///  а) -1  - слева (отрицательный CrossProduct)
	///  б)  0  - прямая пересекает сегмент или лежит прямо на нем
	///  в)  1  - справа (положительный CrossProduct)
	/// Значение ненулевое только когда прямая проходит через одну вершину или не пересекает сегмент
	/// </summary>
	/// <param name="segment"></param>
	/// <param name="v1"></param>
	/// <param name="v2"></param>
	/// <returns></returns>
	private ClipInfo ClipSegment( int segment, Vector2 v1, Vector2 v2 )
	{
		ClipInfo info = new ClipInfo();
		info.clipIndex = -1;

		int nextIndex = MathUtils.WrapIndex( segment + 1, points.Count );

		Vector2 p1 = points[ segment ];
		Vector2 p2 = points[ nextIndex ];

		float combinedTolerance = MathUtils.EPSILON * Mathf.Max( 1f, p1.x, p1.y, p2.x, p2.y, v1.x, v1.y, v2.x, v2.y );

		Vector2 L = v2 - v1;
		Vector2 P = p2 - p1;

		Vector2 D1 = p1 - v1;
		Vector2 D2 = p2 - v1;

		float LxD1 = MathUtils.CrossProduct( L, D1 );
		float LxD2 = MathUtils.CrossProduct( L, D2 );

		// Прямая проходит через вершину 1
		if ( Mathf.Abs( LxD1 ) < combinedTolerance )
		{
			info.clipIndex = segment;
			info.side1 = 0;
		}
		else
		{
			info.side1 = LxD1 < 0f ? -1 : 1;
		}

		// Прямая проходит через вершину 2
		if ( Mathf.Abs( LxD2 ) < combinedTolerance )
		{
			info.clipIndex = nextIndex;
			info.side2 = 0;
		}
		else
		{
			info.side2 = LxD1 < 0f ? -1 : 1;
		}

		info.rightIn = info.side1 < 0 && info.side2 > 0;
		info.rightOut = info.side1 > 0 && info.side2 < 0;
		info.parallel =  info.side1 == 0 && info.side2 == 0;
		
		// Клипим нормально
		if ( info.rightIn || info.rightOut )
		{
			Vector2 clipVertex = new Vector2();
			if ( !Intersection.Intersect_Lines( v1, v2, p1, p2, ref clipVertex ) )
				throw new UnityException( "Прямая и сегмент параллельны, такого не должно быть" );
			
			points.Insert( nextIndex, clipVertex );
			info.clipIndex = nextIndex;
		}

		return info;
	}
#endif
}
